图论建模是将现实世界的复杂连接关系（如互联网路由、状态转换）抽象为数学对象 $G = (V, E)$ 的过程。通过将实体定义为Đỉnh (Vertex) 并将关系定义为Cạnh (Edge)chúng ta có thể sử dụng kiểu dữ liệu trừu tượng (ADT) và thuật toán thống nhất để giải quyết nhiều vấn đề khác nhau.
Định nghĩa các thành phần chính
- Đỉnh (Vertex): Còn được gọi là nút. Có "khóa" (Key) làm định danh duy nhất và có thể mang theo "thông tin dữ liệu" (Payload).
- Cạnh (Edge): Kết nối hai đỉnh, biểu thị mối quan hệ giữa chúng. Có thể là một chiều (đồ thị có hướng) hoặc hai chiều.
- Trọng số (Weight): Giá trị trên cạnh, đại diện cho chi phí (ví dụ như khoảng cách, độ trễ, băng thông).
Tính nghiêm ngặt về mặt toán học
Về mặt toán học, $G = (V, E)$. Trong đó $V$ là tập hợp các đỉnh, còn $E$ là tập hợp các cặp nhị phân $(v, w)$ tạo thành các cạnh, với $v, w \in V$. Cấu trúc trừu tượng cao này cho phép chúng ta sử dụng cùng một bộ thuật toán BFS/DFS để giải quyết mọi vấn đề từ điều hướng bản đồ đến gợi ý mạng xã hội.
Gợi ý mô hình hóa: Đồ thị không gian trạng thái
Khi giải các bài toán đố logic (ví dụ như bài toán bình nước), mỗitrạng thái hợp lệđều là một đỉnh, và mỗi lầnthao tác hợp lệ则是边。解决问题的过程就是寻找从初始顶点到目标顶点的路径。